#pragma once
#include<bitset>
#include<string>
using namespace std;
struct BKDRHash
{
    size_t operator()(const string& s)
    {
        // BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};

struct APHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (long i = 0; i < s.size(); i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

struct DJBHash
{
        size_t operator()(const string & s)
        {
            size_t hash = 5381;
            for (auto ch : s)
            {
                hash += (hash << 5) + ch;
            }
            return hash;
        }
    };
	template<size_t N,class K=string,class Hash1= BKDRHash,class Hash2= APHash,class Hash3= DJBHash>
	class BloomFilter
	{
	public:
        void Set(const K& key)
        {
            size_t x = Hash1()(key) % N;
            bts.set(x);
            size_t y = Hash2()(key) % N;
            bts.set(y);
            size_t z = Hash3()(key) % N;
            bts.set(z);
        }

        bool test(const K&key)
        {
            size_t x = Hash1()(key) % N;
            if (bts.test(x) == false) return false;
            size_t y = Hash2()(key) % N;
            if (bts.test(y) == false) return false;
            size_t z = Hash3()(key) % N;
            if (bts.test(z) == false) return false;
        }
	private:
		bitset<N> bts;
	};

